package 图;

import java.util.ArrayList;
import java.util.List;

/**
 * 207. 课程表
 *你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 * 解题思路：
 *  这道题需要判断课程安排的依赖关系是否合理，即是否存在循环依赖。
 *  我们可以将课程及其依赖关系转化为有向图，通过拓扑排序判断是否存在环。如果存在环，则无法完成所有课程；否则可以完成。
 *  采用 Kahn算法 进行拓扑排序的步骤如下：
 *  1、建邻接表：表示有向图，并统计每个节点的入度。
 *  2、初始化队列：将所有入度为0的节点加入队列。
 *  3、处理节点：依次从队列中取出节点，处理其邻接节点，减少它们的入度。若邻接节点入度变为0，则加入队列。
 *  4： 判断结果：若处理的节点数等于总课程数，则无环，否则存在环。
 *  复杂度分析
 * 时间复杂度：O(V + E)，其中 V 为课程数（numCourses），E 为先修关系数（prerequisites长度）。遍历所有节点和边各一次。
 * 空间复杂度：O(V + E)，邻接表存储所有边，队列和入度数组占用 O(V) 空间。
 *
 * 或者使用DFS的思路实现：
 * DFS 解题思路
 * 使用 DFS 检测环 的思路：
 * 1构建邻接表：表示有向图，记录每个节点的后继节点。
 *
 * 2状态标记：利用 visited 数组标记每个节点的状态：
     * 0: 未访问
     * 1: 正在访问（当前 DFS 路径中）
     * 2: 已访问（已完成检查，无环）
 *
 * 3DFS 遍历：对每个未访问的节点进行 DFS，若在遍历中发现当前路径中存在环（遇到状态为 1 的节点），则返回 false。
 *
 */
public class L_207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> adj = new ArrayList<>();
        // 初始化邻接表的大小
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // 构建领接表（bi -》 ai 的边） -- 保存每一个课程的所有先修课程，构建为一个有向图
        for (int[] prereq: prerequisites){
            int ai = prereq[0];
            int bi = prereq[1];
            adj.get(bi).add(ai);
        }
        int[] visited = new int[numCourses];
        //3: 对每一个未访问的节点进行状态标记 (如果发现有环就返回false，证明无法满足条件)
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && !dfs(adj, visited, i)){
                return false; // 存在环，返回false
            }
        }
        return true;
    }

    // 2:采用dfs进行状态标记

    /**
     *
     * @param adj 邻接表，表示有向图
     * @param visited 状态标记数组，判断当前节点是否被访问过
     * @param u 当前节点的下标
     * @return
     */
    private boolean dfs(List<List<Integer>> adj,int[] visited,int u){
        visited[u]=1; // 标记为正在访问
        // 遍历当前节点的邻接节点
        for (int v : adj.get(u)){
            if (visited[v]==1){
                return false; // 存在环，返回false
            }
            // 如果邻接节点未被访问，递归调用dfs，递归存在环也返回false
            if (visited[v]==0 && !dfs(adj,visited,v)){
                return false;
            }
        }
        visited[u]=2; // 标记为已访问(无环)
        return true;
    }
}
